home *** CD-ROM | disk | FTP | other *** search
/ Giga Games 1 / Giga Games.iso / net / vir_real / faq / publctns / graphics.hck < prev    next >
Encoding:
Text File  |  1992-01-26  |  1.6 KB  |  38 lines
  1. In article <1991Apr3.193547.15558@milton.u.washington.edu>, mitchell@mitre.org (
  2. Richard B. Mitchell) writes:
  3.  
  4. > I have thought
  5. > about dividing the world into subworlds and only "polling" those objects
  6. > that are in the same subworld as the hand.  This seems ok until we
  7. > want ot move an object from one point in space to another.  I have
  8. > also considered using some sort of quad trees, but this does not seem
  9. > like the right approach either.  If any one has any ideas or pointers
  10. > to solutions, I would be grateful.
  11. > 
  12. > ------------------------------------------------------------------------------
  13. -
  14. > Richard B. Mitchell                                    mitchell@linus.mitre.or
  15. g
  16.  
  17.  
  18. You should find Hanan Samet's recent pair of books on spatial data structures
  19. quite useful. I think these grew out of the article "The Quadtree and 
  20. Related Data Structures" in Computing Surveys, v16,2 June 84 p187.
  21.  
  22. My favourites are k-d trees, especially netted k-d trees which were first 
  23. described by J.L. Bentley: "Multidimensional Binary Search Trees used for
  24. Associative Searching", CACM 18(9), Sept 75, pp. 509-517. An application to
  25. a geographical information system was given in the paper Matsuyama, Hao and
  26. Nagao, "A File Organisation for Geographic Information Systems based on
  27. Spatial Proximity", Computer Vision, Graphics and Image Processing 26(3),
  28. June 84, pp 303-318.
  29.  
  30. Other more regular structures like octrees have been used quite a lot for 
  31. ray tracing: examples will be found in Andrew Glassner's book, called something
  32. like "An Introduction to Ray Tracing".
  33.  
  34. Regards,
  35.  
  36.   Matthew Chalmers
  37.  
  38.